One of authentication technologies is a method using challenge and response (Patent Literature 1). In authentication by conventional challenge and response, (1) first, a device to be authenticated, which requests authentication, sends an authentication request to an authentication device, (2) the authentication device sends a challenge value to the device to be authenticated in response thereto, and (3) the device to be authenticated sends a response value for this challenge value to the authentication device. (4) The authentication device checks the response value against the challenge value, and the authentication device decides that authentication has succeeded when the response value corresponds to the challenge value; otherwise, the authentication device decides that authentication has failed. The authentication device sends an authentication result to the device to be authenticated.